package features.advance.leetcode.array.hard;

import features.advance.leetcode.array.BIT;

import java.util.Arrays;

/**
 *  剑指 Offer 51. 数组中的逆序对
 *
 *  难度：困难
 *
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
 * 输入一个数组，求出这个数组中的逆序对的总数。
 *
 *
 * 示例 1:
 *
 * 输入: [7,5,6,4]
 * 输出: 5
 *
 *
 * 限制：
 *
 * 0 <= 数组长度 <= 50000
 *
 * @author LIN
 * @date 2021-07-07
 */
public class Offer51 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            /**
             * 离散化树状数组
             * @param nums
             * @return
             */
            @Override
            public int reversePairs(int[] nums) {
                int n = nums.length;
                int[] tmp = new int[n];
                System.arraycopy(nums, 0, tmp, 0, n);
                // 离散化
                Arrays.sort(tmp);
                for (int i = 0; i < n; ++i) {
                    nums[i] = Arrays.binarySearch(tmp, nums[i]) + 1;
                }
                // 树状数组统计逆序对
                BIT bit = new BIT(n);
                int ans = 0;
                for (int i = n - 1; i >= 0; --i) {
                    ans += bit.query(nums[i] - 1);
                    bit.update(nums[i]);
                }
                return ans;
            }



        };

        int[] nums = {7,5,6,6,4};
        int reversePairs = solution.reversePairs(nums);
        System.out.println(reversePairs);
    }

    static class Solution {
        /**
         * 分治，归并排序
         * @param nums
         * @return
         */
        public int reversePairs(int[] nums) {
            int len = nums.length;

            if (len < 2) {
                return 0;
            }

            int[] copy = new int[len];
            for (int i = 0; i < len; i++) {
                copy[i] = nums[i];
            }

            int[] temp = new int[len];
            return reversePairs(copy, 0, len - 1, temp);
        }

        private int reversePairs(int[] nums, int left, int right, int[] temp) {
            if (left == right) {
                return 0;
            }

            int mid = left + (right - left) / 2;
            int leftPairs = reversePairs(nums, left, mid, temp);
            int rightPairs = reversePairs(nums, mid + 1, right, temp);

            if (nums[mid] <= nums[mid + 1]) {
                return leftPairs + rightPairs;
            }

            int crossPairs = mergeAndCount(nums, left, mid, right, temp);
            return leftPairs + rightPairs + crossPairs;
        }

        private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
            for (int i = left; i <= right; i++) {
                temp[i] = nums[i];
            }

            int i = left;
            int j = mid + 1;

            int count = 0;
            for (int k = left; k <= right; k++) {

                if (i == mid + 1) {
                    nums[k] = temp[j];
                    j++;
                } else if (j == right + 1) {
                    nums[k] = temp[i];
                    i++;
                } else if (temp[i] <= temp[j]) {
                    nums[k] = temp[i];
                    i++;
                } else {
                    nums[k] = temp[j];
                    j++;
                    count += (mid - i + 1);
                }
            }
            return count;
        }
    }
}
